package com.JingYan.HuaWei;

import jdk.nashorn.internal.objects.annotations.Where;
import org.elasticsearch.common.recycler.Recycler;

import java.util.*;

/**
 * @program: JingYan
 * @ClassName: JKC005.java
 * @author: DongJiaQi
 * @version: 1.0.0
 * @Description: 华为机考C卷 多依赖任务
 * @createTime 2024年04月15日 16:28:00
 */
public class JKC005 {
    /**
     * 一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。
     * 现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。
     * 例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：A任务，E任务，B任务，C任务，D任务。这里A和E任务都是没有依赖的，立即执行。
     */

    public static void main(String[] args) {
        // 定义任务依赖关系
        Map<Character, List<Character>> dependencies = new HashMap<>();
        dependencies.put('A', new ArrayList<>());
        dependencies.put('B', Arrays.asList('A'));
        dependencies.put('C', Arrays.asList('A'));
        dependencies.put('D', Arrays.asList('B', 'C', 'E'));
        dependencies.put('E', new ArrayList<>());
        dependencies.put('F', Arrays.asList('A'));
        dependencies.put('G', Arrays.asList('E'));

        List<Character> executionOrder = findExecutionOrder(dependencies);
        System.out.println("任务执行顺序: " + executionOrder);
    }

    private static List<Character> findExecutionOrder(Map<Character, List<Character>> dependencies) {
        List <Character> list = new ArrayList<>();
        HashSet<Character> exeSet = new HashSet<>();
        while (exeSet.size() < dependencies.size()){
            List<Character> bxList = new ArrayList<>();
            for (Character character : dependencies.keySet()) {
                if(exeSet.contains(character)){
                    continue;
                }
                if(dependencies.get(character).stream().allMatch(exeSet::contains)){
                    bxList.add(character);
                }
            }
            bxList.sort(Character::compareTo);
            for (Character character : bxList) {
                list.add(character);
                exeSet.add(character);
            }
        }


        return list;
    }

   /*  public static List<Character> findExecutionOrder(Map<Character, List<Character>> dependencies) {
        List<Character> executionOrder = new ArrayList<>();
        Set<Character> executed = new HashSet<>();

        while (executed.size() < dependencies.size()) {
            List<Character> readyTasks = new ArrayList<>();
            for (Character task : dependencies.keySet()) {
                if (!executed.contains(task) && dependencies.get(task).stream().allMatch(executed::contains)) {
                    readyTasks.add(task);
                }
            }
            readyTasks.sort(Character::compareTo);
            for (Character task : readyTasks) {
                executionOrder.add(task);
                executed.add(task);
            }
        }

        return executionOrder;
    } */
}
